1. Related Art
The related art on which this patent specification is based is described in German Patent Application 196 54 846.2-53 (Method of automatic dynamic reloading of dataflow processors (DFPs) and modules having a two- or multidimensional programmable cell matrix (FPGAs, DPGAs, etc.) and in German Patent Application 196 54 593. 5-53 (Run-time reconfiguration method for programmable modules). A method of configuring and reconfiguring DFPs, as well as FPGAs, DPGAs and similar modules according to the related art in which a separately configured central higher-order microcontroller-like module assumes the task of distribution of configuration data to a plurality of lower-order, mostly passive control units is described in these documents.
2. Disadvantages of the Related Art
By using a central global unit which controls the reconfiguration of parts (e.g. cells (CELs)) of one or more modules, bottlenecks occur when a plurality of different reconfiguration requests are to be handled at the same time. The advantages of the parallelism of the above-described modules are considerably limited by such a central unit, since it represents the typical bottleneck and substantially slows down the processing of data.
Furthermore, assigning the event source to the configuration to be loaded represents a problem because absolute addresses of the configuration memory are used. The reconfiguration unit must therefore contain a type of memory management system which, like in an operating system, also documents which memory area is used by which configuration.
Management of resources (e.g. CELs) represents an additional problem. It must be ensured that each CEL is assigned exactly once to each algorithm started by a reconfiguration request and, specifically, to the one that also uses the remaining surrounding CELs; otherwise deadlocks may occur.
In order to elucidate the problem of reconfiguration again, the following example is given: a matrix of CELs is reconfigured and in the RESET state. Each CEL is capable of indicating whether it is in a reconfigurable state. All CELs in the matrix are ready to be configured; thus they are in a reconfigurable state. A first configuration routine (KR1) is loaded; the matrix is not fully utilized. The configured CELs clear the indication that they are in a configurable state. A second configuration routine (KR2) independent of the first one is loaded in a group of not yet configured CELs. A third configuration cannot be loaded, since this requires CELs of the first and/or second configuration routine (KR3); however these are not in a reconfigurable state as they are being used.
KR3 must be stopped until the required CELs are released, i.e., KR1 and KR2 are terminated.
During the execution of KR1 and KR2, a load request for a fourth configuration routine (KR4) and a fifth configuration routine (KR5) arrives, which cannot all be loaded immediately, because they use CELs that are being used by KR1 and KR2. KR3 and KR4 partially use the same CELs; KR5 uses none of the CELs of KR3 and KR4.
In order to properly reload KR3-KR5, the following requirements must be met:
1. KR3-KR5 should be loaded in the order of the load requests if possible.
2. As many KRs as possible that are independent of one another, i.e., have no common CELs, should be loaded in order to achieve maximum parallelism.
3. The KRs should not block one another, i.e., KR3 is partially loaded but cannot be loaded any further since other CELs are blocked by the partially loaded KR4; while KR4 also cannot be loaded further since again required CELs are blocked by KR3. This results in a typical deadlock situation.
4. The compiler which generated the KRs cannot recognize and cancel the interaction over time of the KRs so that no conflict situation arises.
The ratio between the cost of a circuit to be implemented and an optimum result should be as good as possible, i.e., the object of the invention is to provide a flexible, parallel, deadlock-free configuration that can be executed using moderate time and computing resources at a low cost. In this context the following basic problems must be solved:
if only KR3 were to be loaded, the process would be deadlock free but not optimum since KR5 could also be loaded.
if KR3 is loaded but KR4 is not, and KR5, KR4 must be pre-marked so that it has the highest priority in a subsequent loading sequence, which means high overhead.
Deadlock-free operation is ensured by the following procedure:
The basic object of the present invention is a unit, hereinafter referred to as configuration table (CT), which has a hierarchical structure and may occur several times at each level, the number of CTs from the lowest hierarchical level to the highest diminishing so that exactly one CT is present at the highest level. Each CT configures and controls independently from others and in parallel a plurality of configurable elements (CELs). CTs of the higher hierarchical levels can buffer configuration routines for lower-level CTs. If more than one lower-level CT requires the same configuration routine, it is buffered in a higher-level CT and retrieved by the individual CTs, the higher-level CT retrieving the respective configuration routine only once from a global common configuration memory whereby a cache effect is achieved. In addition to configurable modules, the present invention can be used as a cache procedure for instruction and data cache in microprocessors, DFP or the like having a plurality of arithmetic units. Some of the units to be described below may be omitted depending on the application (e.g., FILMO) however, basically nothing is changed in the hierarchical structure. Therefore this application is considered a subset and is not described in detail. One considerable advantage of the method described over conventional cache procedures is that data and/or codes are cached selectively, i.e., using methods adapted accurately to the algorithm.
The present invention also allows large cell structures to be reconfigured in a completely deadlock-free manner.
Instead of integrating, as previously, a central and global unit in one module, with this unit processing all the configuration requests, there is a plurality of hierarchically (tree structure) arranged active units which can assume this task.
A request from the lowest level (the leaves in the hierarchy) is forwarded to the next higher level only if the request could not be processed. These steps are repeated for all the levels present until the highest level is reached.
The highest level is connected to an internal or external higher-level configuration memory which contains all the configuration data required by this program run.
Due to the tree structure of the configuration units a kind of caching of the configuration data is achieved. Accesses to configurations mainly occur locally. In the most unfavorable case, a configuration must be loaded from the higher-level configuration memory if the corresponding data is not available in any of the hierarchically arranged CTs.
Deadlocks are avoided in that a fixed time sequence of the configurations to be loaded is introduced and the configurations are combined to form a list. The status information of the CELs is saved prior to loading and thus remains unchanged during the processing of the entire list of configurations.
A configuration table (CT) is an active unit which responds to sync signals, known as triggers. The triggers are generated by a two- or multi-dimensional matrix of electronic components usually for arithmetic or logical units, address generators, arithmetic units, and the like, hereinafter referred to as configurable elements (CEL). The trigger that occurs triggers a certain action within the CT. The task of the CT is to assume the control of a plurality of CELs and to determine their arithmetic and/or logical operations. In particular, CELs must be configured and reconfigured. A CT assumes this task by managing a plurality of possible configuration routines (KR) which in turn each contain a plurality of individual configuration words (KW) and configure [sic] a plurality of CELs on the basis of the trigger conditions using one or more KR. Each CEL receives one or more configuration words, which are provided with the address of the CEL to be configured. A KR must be fully and correctly mapped to a plurality of CELs; a plurality of CELs can be combined to form groups; these groups are configured using different but fully executed KRs. All CELs in a group are interconnected so that after a necessary reconfiguration has been determined it is communicated to all the grouped CELs, via a common signal (ReConfig), that each CEL must terminate data processing and go into a reconfigurable state.
Basic Principles of the Deadlock-free Reconfiguration
In systems that are reconfigurable in runtime the problem arises that the system may enter a state in which two parts wait for each other, thus creating a deadlock situation.
This problem could be avoided by only loading a new configuration always entirely or not at all into the system or by using a type of timeout procedure.
This entails a series of disadvantages (space requirements, running time, etc.) and problems such as:
procedure if a configuration cannot be loaded.
managing the order in which the configurations are loaded.
deteriorated performance, since other configurations that could possibly be loaded into the CELs are not taken into account.
These problems can be eliminated with the method described in the following. The starting point is a DFP system according to the related art.
A trigger signal is transmitted from a CEL to a CT. This CT determines the trigger source and selects a configuration (KR)to be loaded using a lookup table. The incoming trigger signals are blocked, and no further triggers are accepted until the current configuration is completely processed. A configuration contains a plurality of commands which are transmitted to a number of CELs. In a system configurable in runtime it is, however, not guaranteed that each configuration command (KW) can also be executed. Impossibility of execution may be caused, for example, by the fact that the addressed configurable element (CEL) has not yet completed its task and thus cannot accept any new configuration data. In order to avoid performance deterioration, all configuration commands that could not be processed (since the respective CELs were not in a reconfigurable state and rejected the configuration (REJECT)) are written according to the FIFO principle in a configuration command located in a special memory (FILMO) (to be described in detail below) after the last command. Subsequently the next configuration command is executed by the same procedure. This is repeated until the end of a configuration has been reached.
Subsequently, the CT assumes a state in which it accepts trigger signals allowing it to continue to load configurations. In this state, the CT processes the FILMO in regular intervals under the control of a timer.
The configurations to be loaded are prioritized by the fact that the CT runs through the FILMO memory before the configuration to be actually loaded is processed. A FIFO-like structure of the FILMO ensures that KWs which could not be fully processed during previous trigger requests automatically obtain a higher priority with respect to the new to be processed. When the FILMO memory is processed each configurable element (CEL) addressed by a configuration command is tested prior to or during the transmission of a KW to see whether it is in the xe2x80x9creconfigurablexe2x80x9d state. If this state is xe2x80x9creconfigurablexe2x80x9d (ACCEPT), the data is transmitted and deleted from the FILMO memory. If the state is xe2x80x9cnot reconfigurablexe2x80x9d (REJECT), the data remains in FILMO and is processed again in the next run. The CT processes the next entry in FILMO.
This is repeated until the end of the FILMO is reached. Then the actual configuration activated by the occurrence of the trigger signal is processed. The structure of the FILMO corresponds to the FIFO principle, i.e., the oldest entry is processed first. In order to process the FILMO even when no new KR is loaded, the FILMO is run through in regular intervals under the control of a timer.
The other, uninvolved configurable elements (CEL) continue to work simultaneously during this phase without their function being affected. Thus it may occur that while the CT processes the FILMO, one or more configurable elements (CELs) change to the xe2x80x9creconfigurablexe2x80x9d state. Since the CT with the processing may be at any location within the FILMO, the following may occur:
The CT attempts to process a first command whose addressed element to be configured (CEL) is not in the xe2x80x9creconfigurablexe2x80x9d state. Therefore, the CT continues with the next command (KW). At the same time one or more configurable elements change to the xe2x80x9creconfigurablexe2x80x9d state, among them also the configurable element which could have been written via the first configuration command. The CT processes a second configuration command (KW), which uses the same configurable element (CEL) as the first configuration command, however originates from another configuration. At this time, the configurable element (CEL) is in the xe2x80x9creconfigurablexe2x80x9d state and the command can be processed successfully.
This no longer ensures that the configuration which should have been loaded first is actually completed first. Two partially completed configurations can now exist each of which requires configurable elements of the other configuration in order to be fully loaded. A deadlock situation has occurred, which is illustrated in FIG. 18. Configuration A and configuration B are to be configured. The CT has already loaded the crosshatched part of configuration A and configuration B. Configuration A still requires the light double shaded area of configuration B for completion and configuration B still requires the dark double shaded area of configuration A for completion. Since neither configuration is fully completed and thus functional, the termination state in which one of the two configurations would be removed does not occur for either of the two configurations. Both configurations are waiting the for the release of the configurable elements still needed.
In the present method a deadlock is prevented in that the CT detects the states of all configurable elements prior to processing the FILMO and then allows no more changes or ignores the changes that occur until the sequence is completed. In other words, either the states of all configurable elements are saved prior to processing the FILMO or a status change is prevented while the FILMO is being processed. One possible technical implementation is the use of a register in each configurable element in which the status prior to processing the FILMO is saved. The CT only works on the basis of the states detected and not with the current states of the configurable elements. This ensures that each command (KW) to be processed is faced with the same state of the configurable elements (CELs). This step does not rule out that one or more configurable elements switch to the xe2x80x9creconfigurablexe2x80x9d state while the FILMO is being processed. This change, however, is not immediately visible to the CT during processing, but only when the next run begins.
Configuration Sequences
In order to configure certain algorithms, it is absolutely necessary to strictly observe the order in which the KW are written in the CEL. For example, it is recommended that the bus system be configured first before a CEL is connected to a bus system, so that the CEL is not connected to a bus used by another routine. In other words, a CEL is only configured if the respective bus links have been previously configured.
In the method according to the present invention, a fixed sequence is observed as follows:
Configuration words (KWs) whose execution is decisive for the configuration of the subsequent KWs are especially marked (and referred to as KWR below). If the configuration of such a KWR fails, all subsequent KWs within the respective configuration routine (KR) are written to the FILMO and are not executed in this run. Even when running through the FILMO, all KWs located in the sequence behind a KWR whose configuration failed are not executed in the current run.
Cache Procedure
The CT has a hierarchical structure, i.e., there are several CT levels in a module. The arrangement is preferably a tree structure (CT tree). An external configuration memory (ECR), containing all KRs is assigned here to the root CT, while the configurable elements (CELs) which call up the individual KRs are assigned to the leaves. The configurable elements are assigned to the mid-level CTs of the same hierarchical level. A local internal memory is assigned to each CT. This memory is partially cleared when there is no more space for new KRs to be stored or when this is explicitly requested by a special CT command (REMOVE). The memory is clared one KR at a time using a delete strategy such that in the ideal case only those KRs are deleted that are no longer requested or are explicitly identified in the REMOVE command. The number of KRs deleted individually is such as to free the exact amount of memory space required to write the new KRs to be loaded into the memory. As a result, as many KRs as possible remain in the memory to optimize the cache effect.
The advantage is that the each CT subordinate to any desired CTx and thus located further up in the CT tree does not request a KR stored in the CTx from the external configuration memory ECR but obtains it directly from CTx. This results in a cache structure over several levels. The data transmission overhead in the CT tree, in particular the required ECR memory bandwidth, is considerably reduced.
In other words, each CT buffers the KRs of the CT below it. This means that the lower level CTs obtain the required KRs directly from those above them, and no memory access to the external ECR is necessary. Only if a required KR is not available in one of the higher level CTs must the KR be loaded by accessing the ECR. This results in a particularly efficient hierarchical cache structure for KRs.
This structure also results in delete strategy options which however should be determined empirically, depending on the application. These options include:
deleting the oldest entries
deleting the smallest entries
deleting the largest entries
deleting the entries retrieved least often.
Basic Principles of the Ct Hierarchies
In order to achieve a cache effect, CTs are connected together to form a hierarchical tree structure. A bus system (inter-CT bus) connecting an upper node (CT) to a plurality of lower nodes (CTs) is located between the individual nodes (CTs). Lower nodes (CTs) request data from the upper nodes (CTs); the upper nodes then send data to the lower nodes. The lower nodes exchange status information using the networks between the higher nodes which therefore must resolve the addresses.
Ct Hierarchies and Addressing
CT hierarchies are arranged so that a binary tree can be used for addressing the individual CTs. This means that the least significant address bit identifies the individual leaves of the tree and each additional address bit selects the next higher hierarchical level. Thus, each CT has a unique address.
The following table shows how the individual address bits are assigned to the respective levels:
If a higher level CT is assigned to a group of CTs, multiple address bits of the group are combined accordingly.
The following table shows how the individual address bits are assigned to the respective levels; a group with 8 CTs is located on level 0. (Address bit 2-0):
The binary tree can have an unidimensional or multidimensional structure by having one binary tree for each dimension.
A certain CT (TARGET) is addressed in that the initiating CT (INITIATOR) either provides the exact target address or uses the relative TARGET address.
The evaluation of a relative address is described in more detail below.
Example of a relative address field for a two-dimensional addressing:
Bit 15 is set when the CT of the next higher hierarchical level is to be selected.
Bit 14 identifies broadcasts, i.e., selects all CTs.
The X/Y addresses provide the address of the TARGET based on the address of the INITIATOR.
The addresses are xe2x80x9csignedxe2x80x9d (plus or minus) integers. The TARGET is determined by adding the Y/X addresses of the address field to the current address position. Each level has a certain address width. The adders correspond to this width.
Overrun or underrun during addition means that the addressed CT is not below the current node and the address request is forwarded to the CT above it (the next higher node).
If no overrun or underrun occurs, TARGET is below the current node. The address bit calculated on the current level (see tables) selects the CT located directly below the current node. The next lower CT (node) is selected from this CT using the correspondingly calculated address bit.
Prioritizing Access in Ct Hierarchies
Access to the inter-CT bus is managed by an arbiter. All lower nodes have the same priority. The upper node has a higher priority. Therefore, an access transmitted from a higher node downward or one that has already covered a long distance from the INITIATOR is prioritized over other accesses.
Basic Structure of a CT
The following description of the CT provides an overview of the individual components. The detailed description of the main groups is given below.
The core of a CT is the control state machine (CTS) which controls all configuration routine (KR) processing. The garbage collector (GC) which controls the removal of KR from the memory (CTR) of the CT; the FILMO which assumes the management of the KWs still to be processed, and the LOAD state machine which controls the loading of KRs are assigned to the CTs.
The memory (CTR) is designed as a conventional read-write memory where all technically possible implementations may be used, and is used for local storage of KRs for the respective CT and the CTs subordinate to it. As a special case, the memory (CTR) can also be designed as a ROM, EPROM, EEPROM, flash ROM, or the like, in order to provide the module with a fixed, ASIC or PLD-type (see Background information) function.
In order to generate the CTR addresses, four pointers configured as loadable counters are used:
1. Free Pointer (FP). Points to the first free memory location after the last KR in the CTR.
2. Garbage Pointer (GP). Points to an entry to be removed by the garbage collector (GC) from the CTR.
3. Move Pointer (MP). Points to the memory location in the CTR from which a valid configuration word (KW), not to be removed, i.e., an entry of a KR, is to be copied/moved to the entry defined by the GP.
4. Program Pointer (PP). Points to the KW currently being executed by the CTS.
KWs are forwarded to the respective CELs via an output interface (OUT). The CELs acknowledge (ACCEPT) the receipt of the KW, provided they are in a reconfigurable state. If a KW is not acknowledged (REJECT) it is temporarily buffered in a FIFO-like memory (FILMO) to be written again to the addressed CEL at a later time without using the program pointer.
The CTS receives via trigger signals, a request to process a KR. The trigger signals pass through a mask, i.e. a filter, which filters out (masks out) undesirable triggers. A mask can be designed according to the related art using an AND gate, which links a trigger with an AND enable signal. The triggers are converted into binary signals via a prioritized round-robin arbiter (SCRR-ARB). A prioritized round-robin arbiter combines the advantage of the democratic character of a round-robin arbiter with the recognition of the next enable in a cycle, i.e., the advantage of a priority arbiter.
The masked triggers are switched as an address to a first lookup table (LUT1), i.e., a memory that assigns the ID of the respective KR to the trigger incoming as an address and outputs it over the data lines.
In a second lookup table (LUT2) the ID of the KR is assigned to the address of the memory location of the KR in the CTR. The second lookup table is used not only for assigning trigger signals, but commands using an ID as a parameter also use the LUT2 for address assignment.
The assignment of the trigger signals to the respective IDs is entered into LUT2 via the xe2x80x9cREFERENCExe2x80x9d command to be described later. LUT2 is managed, i.e., the IDs are assigned t o the addresses in CTR, automatically by the CTS and the GC.
To better understand the CT, a possible basic set of commands is illustrated below:
1. BEGIN  less than ID greater than 
BEGIN  less than ID greater than  denotes the start of a configuration routine.  less than ID greater than  provides the unique identification number of the configuration routine.
2. STOP
STOP denotes the end of a configuration routine. At this point the configuration table (CT) terminates the processing of the configuration routine. The garbage collector (GC) terminates the removal of entries of this configuration routine.
3. EXECUTE  less than ID greater than 
Jumps to the start (BEGIN  less than ID greater than ) of a configuration routine. If this routine is not present in the CT memory, it is requested from the next higher CT, or loaded from the memory.
4. LOAD  less than ID greater than 
Requests the KR  less than ID greater than  from the next higher CT.
5. REMOVE  less than ID greater than 
Calls the GC in order to remove the configuration routine  less than ID greater than  from BEGIN  less than ID greater than  to STOP from the CT memory and pre-write the subsequent configuration routines to the point where no memory hole is created by the removed configuration routine.
6. PUSH  less than FORCED greater than   less than ADDRESS greater than   less than DATA greater than   less than EXIT greater than 
Writes the configuration data  less than DATA greater than  to the  less than ADDRESS greater than  register. If  less than FORCED greater than  is set, data is written even if the RECONFIG flag of the respective target register is not set.  less than EXIT greater than  is used to indicate a KWR which interrupts further execution of the subsequent KWRs in the event of a REJECT.
7. MASK  less than SR greater than   less than TRIGGER greater than 
Sets or resets the trigger mask using  less than TRIGGER greater than  as a function of  less than SR greater than  (Set/Reset).
8. WAIT  less than UNMASKED greater than   less than TRIGGER greater than 
Stops the processing of the configuration routine and waits for  less than TRIGGER greater than . If  less than UNMASKED greater than  is set, there is a response to the expected trigger regardless of the state of the trigger mask.
9. TRIGGER  less than TRIGGER greater than   less than CT# greater than 
Sends the binary value of a trigger to the higher level CT addressed by CT#.
10. GETBUS/GETCTS
Establishes a connection to the inter-CT bus.
11. LOOSEBUS/LOOSECTS
Terminates the connection to the inter-CT bus.
12. REFERENCE  less than TRIGGER greater than   less than ID greater than 
Writes the value  less than ID greater than  into the LUT2 at the address  less than TRIGGER greater than , whereby a certain configuration routine (KR) is assigned to a trigger signal.
The commands EXECUTE, LOAD, REMOVE, PUSH, MASK, WAIT, TRIGGER, REFERENCE are only valid within the BEGINxe2x80x94STOP brackets. The commands are not executed outside these brackets.
A configuration routine (KR) has the following structure:
BEGIN  less than ID greater than ;
. . .
valid commands
. . .
STOP;
Indirect Addressing (Referencing)
The cache principle of the CT allows a KR to be buffered in a CT, the KR being used by a plurality of different lower-level CTs or CELs.
If the lower-level units access the external interface of the module (e.g., RAM, periphery), it becomes necessary to store different addresses or parts of the external interface. This would make the contents of the required individual KRs fundamentally different. Caching is no longer possible.
Indirect referencing provides a remedy. For this purpose, special KR (hereinafter referred to as IKR) are used, which contain and set the required external parameters. Other different KRs may be called up via triggers on different hierarchical levels. The actual KR is called up starting at the end of an IKR. The IKR are not cachable, however, while the KR called up are all uniform and are therefore cachable. It is advisable that the size of the IKR be reduced to the absolute minimum, i.e., only the external and different parameters and the call up of the uniform KRs.
An indirect configuration routine (IKR) is structured as follows:
BEGIN  less than ID greater than ;
. . .
xxx; valid commands where only external peripherals are to be activated,
TRIGGER  less than ID greater than ; start, stop, or load requests to peripheral processes
. . .
GOTO  less than ID greater than  Jump to uniform KRs STOP;
Special Cases:
1. WAIT_FOR_BOOT
This command is only valid at the first address of the CTR. During the boot sequence, the complete boot KR is initially written into the CTR, but not the start sequence of the boot KR BEGIN  less than 0 greater than . In its place (at address 1) is WAIT_FOR_BOOT which is set automatically after a RESET. WAIT_FOR_BOOT is not overwritten with BEGIN  less than 0 greater than  and the CTS does not begin processing the boot KR until the entire boot KR has been written to the CTR.
WAIT_FOR_BOOT should not occur within a program.
2. BOOT  less than CT ID greater than 
BOOT  less than CT ID greater than  marks the CT in which the following boot KR should be written. No BEGIN follows after BOOT  less than CT ID greater than , the boot KR is not terminated by STOP, but by a subsequent BOOT  less than CT ID greater than . A STOP ends the boot sequence.
BOOT  less than CT ID greater than  should not occur within a program.
Boot Sequence
After a RESET, the CT of the uppermost hierarchical level (ROOT CT) loads the boot KR into the CTs of the lower hierarchies. For this purpose, there is a jump to a fixed address (BOOT ADR) in the external configuration memory (ECR) assigned to the ROOT CT. The ROOT CT executes this jump and arrives at the boot sequence. This is structured as follows:
BOOT  less than CT ID0 greater than ; COMMAND; COMMAND; . . .
BOOT  less than CT ID1 greater than ; COMMAND; COMMAND; . . .
BOOT  less than CT ID2 greater than ; COMMAND; COMMAND . . . STOP;
During the boot sequence the complete boot KR is initially written into the CTR starting at address 2 of the CT defined by  less than CT ID greater than . The start sequence of the boot KR (BEGIN  less than 0 greater than ) is not written to address 1. In its place is WAIT_FOR_BOOT which is automatically set after a RESET. STOP is not written to the end of the boot KR in the CTR, overwriting WAIT_FOR_BOOT with BEGIN  less than 0 greater than  until the entire boot KR has been written into the CTR and the ROOT CT has reached the next BOOT  less than CT ID greater than . The CTS starts processing the boot KR.
Loading a Configuration Routine
There are three basic mechanisms for requesting a configuration routine in addition to the boot KR:
1. Execution of a LOAD  less than ID greater than  by the CTS
2. Execution of an EXECUTE  less than ID greater than  by the CTS, the KR with the respective ID not being available in the CTR.
3. Occurrence of a trigger which is translated into an  less than ID greater than  whose respective KR is not available in CTR, via LUT1.
The sequence is the same in all three cases:
The ID of the requested KR is provided as an address to LUT2. LUT2 checks whether a valid address exists in CTR. If it does not exist, i.e.,  less than ID greater than  points to the value 0 in LUT2, load  less than ID greater than  is sent to the CTS.
Subsequently CTS requests the  less than ID greater than  of the respective KR from the hierarchically higher-level CT. This request reaches the higher-order CT in the form of a trigger and is evaluated by it accordingly.
The higher-order CT transmits the requested KR to the requesting CT. The data is written, starting at the address to which FREE-POINTER (FP) points, into the CTR, the FP being incremented by one after each write access.
When FP reaches the upper limit of the CTR, the garbage collector (GC) is called up to remove the lowermost KR within the CTR and to compress the CTR. The FP is reset. This sequence continues until the KR to be loaded fits completely into the CTR.
Jump Table in the Configuration Memory
The configuration memory assigned to ROOT CT contains all the KR that must be loaded for an application. In the external configuration memory (ECR) there is a jump to the boot configuration routine at a fixed address (ADR BOOT). At another fixed address range (LUT ECR) of any desired length which is, however, predefined within an application there are jumps to the individual KRs. The  less than ID greater than  of each KR is used as an address in ECR where the start address of the respective KR is located; thus KRs are addressed indirectly:
IDxe2x86x92LUT ECRxe2x86x92KR
Modifying the Kr in the Configuration Memory
The KR with the ID  less than A greater than  is to be modified. The HOST initially writes the new KR for the ID  less than A greater than  to a free memory location in the ECR. The ID  less than A greater than , together with the new address of the KR, is written in the configuration memory from the higher-level unit (HOST) into a ROOT CT register provided for that purpose. The ROOT CT sends the command REMOVE  less than A greater than  to all CTs below it. Subsequently, when a STOP is reached or during IDLE cycles, i.e., as long as no KR is being executed, all CTs remove the KRs related to this ID from the CTR and set LUT2 at address  less than A greater than  to xe2x80x9cNoAdr,xe2x80x9d which means there are no valid address entries for ID  less than A greater than  in LUT2. If the ID  less than A greater than  is requested again, the missing entry (xe2x80x9cNoAdrxe2x80x9d) at the location  less than A greater than  in LUT2 forces each CT to request the KR  less than A greater than  from the ECR again.
The FILMO
A KR is composed basically of the command PUSH, which writes new configuration words to a certain address. If a configuration word of the type KW cannot be written because the configurable element (CEL) addressed is not ready to receive a new configuration (REJECT), the configuration word is written into a memory hereinafter referred to as FILMO instead of to the configurable element (CEL) addressed. The subsequent commands are processed normally until a configuration word cannot be written again; it is then written into the FILMO.
If a configuration word of the type KWR cannot be written because the configurable element (CEL) addressed is not ready to receive a new configuration (REJECT), the configuration word is written into a memory hereinafter referred to as FILMO instead of to the configurable element (CEL) addressed. All subsequent commands to the end of the KR are written directly into the FILMO, rather than to the CEL.
The entire FILMO is run through in IDLE cycles and before each execution of a new KR. Each word of the FILMO that is read out, beginning with the oldest data word is to be sent to its addressed element according to the known FIFO principle; the addressed element must be ready to receive the configuration word. If the data words can be written from the beginning (i.e., the addressed configurable elements (CELs) are ready), the entry is removed from the FILMO by the FIFO principle. If a configuration word cannot be written, it is skipped and is not removed from the FILMO. Contrary to FIFO, the data after the skipped configuration word continue to be read. The configuration words written after a skipped configuration word can, depending on the implementation of the FILMO, be
1. marked as written and not deleted from FILMO; configuration words marked as written are no longer read during subsequent runs or are immediately deleted if a skipped configuration word is no longer located in front of them; or
2. deleted from the FILMO; the configuration words before and after the deleted configuration word are preserved. The subsequent words must be shifted forward (up) or the previous words must be shifted backward (down) for deletion, the order of the configuration words being preserved in all cases.
If a new KR is executed, the configuration words (KW) which could not be written by the CTS to the addressed elements (CELs) are appended again to FILMO, i.e. the KW are written to the end (in the reading direction) of the FILMO. If the FILMO is full, i.e., there are no free entries for configuration words, the execution of the KR is stopped. The FILMO is run through until a sufficient number of configuration words could be written and a corresponding number of free entries have been created, whereupon the KR continues to be processed.
The FILMO is a FIFO-like memory which is always run through linearly starting from the oldest entry; contrary to a FIFO, however, entries are skipped (First In Linear Multiple Out).
Function of the Configuration Table State Machine (Cts)
The configuration table state machine (CTS) is responsible for controlling the CT. It executes the commands of the KR and responds to incoming triggers. It manages the FILMO by reading the FILMO during IDLE cycles and before executing a KR.
It responds to the signals illegal  less than TRG greater than  (Illegal Trigger, see FIG. 1, 0102) and load  less than ID greater than  generated by the LUT structure. load  less than ID greater than  is generated when a cache miss exists in LUT2 (0105) or the KR/IKR referenced by ID has been marked as deleted (0107). It responds to the control signals of the higher level CT.
An example of implementation for processing the commands is illustrated in FIGS. 2 through 7.
Control Signals to Higher Level Cts
illegal  less than TRG greater than  (0102) shows to the higher level CT that an unknown trigger  less than TRG greater than  has occurred.
load  less than ID greater than  (0105/0107) requests the higher level CT to load the  less than ID greater than .
trigger  less than TRG greater than   less than CT# greater than  (0108) sends a trigger  less than TRG greater than  to the higher level or to the addressed CT  less than CT# greater than .
Control Signals from Higher Level CTs
remove  less than ID greater than  (see FIG. 15, 1513) requests the CT to delete the  less than ID greater than .
write_to_FP  less than data greater than  (see FIG. 2, 0205) sends the data to the CT. The data is appended to the end of the data in the memory.
Function of the Garbage Collector (Gc)
The CTR has two problems:
1. If a LOAD or EXECUTE command or a trigger refers to an ID whose KR is not present in the CTR, the KR must be re-loaded. Sometimes however there is not enough space available in the CTR to load the requested KR.
2. If a REMOVE  less than ID greater than  occurs, the respective KR must be removed from the CTR. This creates a gap unless the KR is located at the end of the CTR. When a new KR is loaded, the gap may not be completely filled again or the gap may be too small for the new KR. This results in fragmenting of the CTR. The function of the garbage collector is to remove KR from the CTR in order to create space for new entries AND to reorganize the CTR after the removal of entries so that all remaining KR are located in succession in the memory as a contiguous block and the freed memory blocks are located at the end of the CTR as a contiguous block.
Thus new KR can be re-loaded in an optimum manner and without loss of memory space.
Evaluating Trigger Pulses
Each CT has a link to a plurality of trigger signals belonging to its respective hierarchical level, which are combined to form a bus. Incoming triggers are evaluated via a mask, i.e. only the enabled trigger signals are forwarded. The enabled trigger signals are buffered in a sample register synchronously with the system clock (sampled). An arbiter selects one of the stored trigger signals and converts the signal into a binary vector. The selected trigger signal is deleted from the sample register. The binary vector is forwarded to a first lookup table (LUT1) which translates the binary vector into the identification number (ID) of the configuration routine (KR) to be called up. The ID is translated into the address of the KR in the CT memory (CTR) in a second lookup table (LUT2). The CT state machine (CTS) sets its program pointer (PP) to this address and begins the execution of the KR. The prerequisite is that each trigger enabled via the mask has a corresponding entry in LUT1. Otherwise an error condition is forwarded to the CTS (illegal trigger); each ID=xe2x80x9cNoAdrxe2x80x9d is evaluated as a non-existing entry. xe2x80x9cNoAdrxe2x80x9d is a token selected depending on the implementation.
If there is no entry in LUT2, i.e., the KR of the respective ID is not in the CTR, a load request is sent to the CTS (load  less than ID greater than ).
Sending Trigger Pulses to the Higher Level CT
In addition to the interface described above to a higher level CT for loading KR, there is an additional interface for exchanging freely definable commands, in particular, however, trigger vectors. A CT sends
either a command to all the other CTs (BROADCAST)
or a command to any addressed CT (ADDRESSED).
The xe2x80x9cTriggervectorxe2x80x9d command represents a binary value that refers to an entry in the LUT2 of the receiving CT.
It is necessary to send trigger vectors in order to start a KR within an IKR in an additional CT, in order to activate the periphery or the memory, for example.
In order to forward trigger vectors to a higher level CT, there are two mechanisms:
1. A bit indicating whether the content of the memory is regarded as a KR ID or as a binary value for a trigger pulse is supplied to LUT1. If a trigger pulse is present, the data content of LUT1 is sent directly to the higher level CT as a trigger.
2. The binary value of a trigger can be indicated with the TRIGGER command which is sent directly to the higher level CT. (As an alternative, IDs can also be transmitted directly instead of a trigger value).
In order to start a KR in another CT via trigger vectors, a synchronization procedure must be created in order to prevent a deadlock. The procedure must make sure that only one KR within a certain group of CTs starts other KRs in other CTs within this group. Starting several KRs at the same time may result in a deadlock among the CTs, similar to the deadlock on the CEL level described above.
In principle such a procedure runs as follows:
A KR is structured as follows:
. . .
GETCTS/GETBUS
TRIGGER  less than ID greater than ,  less than CT# greater than 
TRIGGER  less than ID greater than ,  less than CT# greater than 
. . .
LOOSECTS/LOOSEBUS
. . .
The xe2x80x9cGETCTSxe2x80x9d command within a KR of the CT (INITIATOR) indicates that signals are sent to other CTs (TARGET) in the following. With Trigger  less than ID greater than ,  less than CT# greater than  the ID of a KR to be started is sent to the CT having the unique ID CT#. The trigger is initially sent to the directly higher level CT, which sends the trigger according to the CT# to a lower level CT within its CT space or to its higher level CT (see CT hierarchies). When the command reaches the TARGET, the latter acknowledges receipt.
When the command runs through a CT, a priority ID of the command is incremented by one. If the forward request of a command encounters another request within a CT, the command having the lowest priority is rejected. Thus
a) it is ensured that only one command propagates at any one time within an overlapping system and thus only one KR is started, which prevents deadlock as required;
b) it is ensured that the command that has propagated least far is rejected, which may result in enhanced performance.
After a command has been rejected, all previous commands within the GETCTS/LOOSECTS are also rejected, i.e., INITIATOR sends the DISMISS signal to all TARGETs and the execution of the KR starts again after a wait time upon GETCTS.
The acknowledgments of all triggers within a GETCTSxe2x80x94LOOSECTS command segment are sent to the INITIATOR CT. Processing of the next command continues with each incoming acknowledgment.
When the LOOSECTS command is reached, INITIATOR sends the GO signal to all TARGETS. This starts the execution of the KR having the ID transmitted by the trigger by the TARGET CTs.
After the occurrence of a trigger, TARGETs change to a state in which they wait for the occurrence of a GO or DISMISS signal.
For better implementability, a slightly modified procedure is also presented:
A bus system (inter-CT bus) is located between the CTs in a group of a hierarchical level. This bus system connects all CTs of the group and a CT of the next higher level group.
The bus system is arbitrated by a CT through the GETBUS command which is functionally similar to GETCTS. The commands are forwarded via the bus system to the CTs of the same group. If the addressed CT# is not within the group, the higher level bus is automatically arbitrated by the higher level CT and the command is forwarded. The arbitrated buses remain assigned to INITIATOR and thus blocked for all other CTs until either a reject occurs or the LOOSEBUS command frees the bus. LOOSEBUS is comparable to LOOSECTS. Before executing the LOOSEBUS command, the GO signal is sent to all involved CTs. This is accomplished either through the LOOSEBUS command or through a special command that precedes it. Commands, in particular triggers, are also processed according to the basic procedure described above. A reject occurs if a bus system cannot be arbitrated. The CTs of a certain level have the same priority for arbitration; the higher level CT has a higher priority. When a command is sent via the inter-CT bus, the command remains active until the addressed CT accepts (ACCEPT) or rejects (REJECT) the command.
The Prioritized Round-robin Arbiter
The prioritized round-robin arbiter (single-cycle round-robin arbiter SCRR-ARB) has a clock synchronous structure, i.e. for each (positive or negative depending on the implementation) cycle flank (TF1) it delivers a result. The incoming signals (ARB-IN) pass through a mask (ARB-MASK) which is managed by the arbiter itself by the procedure described below. The output signals of the mask are supplied to a priority arbiter (ARB-PRIO) according to the related art. The arbiter delivers a result (ARB-OUT), synchronized with the system clock, for each cycle flank (TF1), i.e., the binary value of the highest-priority signal after the mask (ARB-MASK). A signal (VALID) which indicates whether the binary value is valid or invalid is assigned to the result. Depending on the implementation of the priority arbiter, it is possible that the same binary value is generated when the signal 0 is present and when no signal is present; in this case VALID indicates that the result is invalid if no signal is present. This signal is
1. output as the result of the arbiter and
2. sent to a decoder which decodes the binary values as shown in the following table for a three-bit binary value as an example. (The coding procedure can be adapted to any desired binary value according to this principle):
A register (ARB REG) which receives the decoded values (ARB DEC) of the decoder at a cycle flank (TF2) that is the inverse of TF1 is assigned to the decoder. ARB DEC is fed back to the mask (ARB MASK) and enables the individual input signals (ARB IN).
The functional sequence in the arbiter is as follows:
1. After a RESET, all ARB IN are enabled via ARB MASK, since ARB DEC sets all signals to xe2x80x9cenablexe2x80x9d.
2. The highest priority ARB IN set (for example signal 7 (binary 111) has the highest priority and 0 (binary 000) the lowest priority in the above table) is output as a binary value.
3. Via ARB DEC the signal is blocked, as are all the other inputs that may have had a higher priority, but are not set.
4. The following steps 5 and 6 are repeated until signal 0 (binary 000) is reached or no signal is present after ARB MASK. Then ARB DEC (see decoding table) enables all signals through ARB MASK via ARB DEC again and the sequence starts at step 2.
5. The ARB IN set that now has the highest priority is output as a binary value.
6. Via ARB DEC the signal is blocked, as are all the other inputs that may have had a higher priority but are not set. (Continues with step 4)
Thus it is achieved that all input signals are handled with the same priority and one of the input signals (ARB IN) is decoded as a binary signal and output (ARB OUT) in each clock cycle. ARB REG can be provided with an enable input (EN) which allows the contents of the register to be changed only at TF2, when a corresponding signal is present. The result is that a binary vector is not output in each cycle, but is output instead as a function of an enable by EN and TF2. The input is needed for synchronization when the downstream circuit cannot perform the processing in one clock cycle, but needs multiple cycles before accepting the next binary vector.
Sometimes it is recommended that the arbiter consider a series of signals as having a higher priority, while the majority of signals have the same priority. This is necessary, for example, in the case of the previously described procedure for forwarding signals between CTs. In order to give a signal a higher priority, the link of the ARB PRIO having the highest priority is not masked, i.e., it bypasses the mask (ARB MASK). Thus the signal is treated preferentially.
Structure of a Microcontroller-based CT
Contrary to the previous descriptions, a CT can also be implemented to have a microcontroller architecture.
It can be easily seen that the basic functions such as trigger control, lookup tables LUT1 and LUT2, as well as the inter-CT communication and writing the KW to the CEL can be readily accomplished by a microcontroller. Only the structure of an efficient FILMO represents a problem which is mainly manifested in the performance that can be achieved. Therefore the structure of the FILMO will be described separately.
Structure of the FILMO
The FILMO is not designed as a separate memory. Instead, the conventional program memory is extended to include FILMO functionality. For this purpose, an additional bit (FILMO BIT) which indicates whether or not the corresponding KW has been written into the CEL is assigned to each KW. If the FILMO BIT is set, the corresponding KW is not executed. When a KW is written into the memory, the FILMO BIT is reset. All KRs within a CT are connected via a chaining list (FILMO LIST) in the order in which they were called up by triggers or LOAD  less than ID greater than . A KR remains in the FILMO LIST until it is fully executed, after which it is removed from the list. The FILMO LIST is run through according to the FILMO procedure and thus represents a direct substitute for the FILMO memory.
(For the sake of completeness we shall note that contrary to the original FILMO procedure no KR may occur twice in the list. If a KR that is still in the FILMO LIST is called up, its execution must be delayed until it is removed from the FILMO LIST.)
The structure of a FILMO memory location is as follows:
Commands
The microcontroller supports the following commands that have a direct influence on the FILMO:
PUSH write a KW to a CEL
PUSHSF write a KW to a CEL and set the FILMO BIT if the KW has been accepted (ACCEPT)
PUSHRET write a KW to a CEL and return (RETURN) from the subroutine if the KW has not been accepted by the CEL (REJECT). This command is used when subsequent KW in the KR are dependent on the configuration of this KW (ACCEPT); their configuration is prevented by the return from the KR until PUSHRET is successful (ACCEPT).
PUSHNR write a KW to a CEL only if no REJECT occurred previously within the KR. Like PUSHRET, PUSHNR is also used to handle dependencies in the order in which the KWs are configurated.
Garbage Collector
As described previously, a garbage collector (GC) is used to remove KRs that are no longer needed. The GC is started either when there is insufficient space in the memory for loading a new KR and IDs must be removed; or when a KR is explicitly deleted by the REMOVE command with the indication of the ID of the KR to be deleted.
In order to configure the GC run as simply as possible, all KRs are connected via a chained list. GC runs through the list and removes the KRs that are no longer needed by overwriting them with other KRs and adjusting the list entries accordingly. All the remaining KR in the memory are shifted so that the memory gap created by the KR to be deleted is closed and a larger contiguous free space is created at the end of the memory.
Structure of a KR
One possible basic structure of a KR is shown in the following table:
At the beginning of the KR, a jump occurs over the following header to the start of the command sequences. It follows the double-chained list for the garbage collector in which all KR are linked to one another. xe2x80x9clengthxe2x80x9d indicates the length of the KR. This information can be used for Block-Move commands according to the related art which are used when the KR have to be moved in the memory (Garbage, Load, etc.).
The FILMO is formed in the following double-chained list; only those KRs that contain KWs which have not yet been written to the CEL are connected to one another.
Statistics on the condition of the cache follow, containing, for example, the number of KR calls (the value is incremented by one for each call), the age (can be measured using the number of GC runs over the KR; the value is incremented by one for each GC run), etc. The GC can evaluate these statistics when a KR must be removed for reasons of memory space. Considerable advantages result for the caches from these statistics. Thus, for example, the microcontroller can be programmed depending on the cache algorithm used according to the requirements of the application so that
1. the oldest/newest KR
2. the smallest/largest KR (see the xe2x80x9clengthxe2x80x9d entry)
3. the least often/most often called KR is deleted from the cache when free memory is needed. Of course, additional appropriate status information can be stored. Such a selective caching is not possible with the cache structures known today. In particular, freely programmable cache algorithms are not supported in caches according to the related art.
In conclusion, there are KR statistics containing, for example, the number of not yet configured (REJECT) or configured (ACCEPT) KWs. At the same time, the address of the first KW yet to be configured can be stored. This has the advantage that in the case of a FILMO run a jump can be made directly to the KW and the complete KR does not have to be run through, which results in a considerably enhanced performance.
In conclusion, it should be noted regarding the KR that the chained lists are preferably built up by entering the previous/next ID, since thus the absolute memory addresses can be easily shifted by the GC. Only relative jumps instead of absolute jumps should be used within a KR in order to avoid problems when loading the KR and during GC runs, since the absolute addresses are modified in those cases.
For the sake of completeness it should also be mentioned that, according to the above-described principle, the FILMO is run through prior to executing a new KR (upon a trigger or command even from another CT) and the status of the CEL (reconfigurable or not) is saved prior to running through the FILMO, also when a microcontroller is used.